package oj;

import java.util.*;

//从中序和后序遍历序列构造二叉树：给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
public class Solution_106 {
    //用 List 解决问题
    public static List<Integer> toList(int[] array){
        List<Integer> list = new ArrayList<>();
        for(int e : array){
            list.add(e);
        }
        return list;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //先将中/后序遍历从数组转换成 List 的形式
        List<Integer> inorderList = toList(inorder);
        List<Integer> postorderList = toList(postorder);

        //返回构建好的树
        return build(inorderList,postorderList);
    }
    //用中序和后序构建二叉树的方法
    public static TreeNode build(List<Integer> inorder, List<Integer> postorder){
        //判断后序遍历是否为空，为空则返回 null
        if(postorder.size() == 0){
            return null;
        }
        //1.先确定根的值
        int rootVal = postorder.get(postorder.size() - 1);
        //2.确定根在中序遍历中的下标,即左子树的结点个数
        int leftSize = inorder.indexOf(rootVal);
        //3.创建根结点
        TreeNode root = new TreeNode((char) rootVal);
        //4.切出左子树的中序遍历和后序遍历
        List<Integer> leftInorder = inorder.subList(0,leftSize);
        List<Integer> leftPostorder = postorder.subList(0,leftSize);
        //使用相同的方法，对左子树进行构造
        TreeNode left = build(leftInorder,leftPostorder);
        //5.切出右子树的中序遍历和后序遍历
        List<Integer> rightInorder = inorder.subList(leftSize + 1,inorder.size());
        List<Integer> rightPostorder = postorder.subList(leftSize,postorder.size() - 1);
        //使用通向的方法，对右子树进行构造
        TreeNode right = build(rightInorder,rightPostorder);
        //6.将左右子树与根关联起来
        root.left = left;
        root.right = right;
        //7.返回构建好的树
        return root;
    }

    public static void main(String[] args) {
        int[] inorder = {9,3,15,20,7};
        int[] postorder = {9,15,7,20,3};
        Solution_106 solution = new Solution_106();
        TreeNode root = solution.buildTree(inorder,postorder);
    }
}
